We live in the information age in which there is a constant flow of information and data. Often times we struggle on a personal level to make sense of the data and avoid information over-load. Similarly, businesses often struggle to manage and properly handle the massive amounts of data that may be generated on a daily basis by business processes. Without mechanisms and tools to handle and process this data, these businesses can easily be overwhelmed by the information.
As can be appreciated, raw data without any structure or form is generally not very useful for businesses. Consequently, there is an increasing need for tools that businesses can use to extract useful business intelligence from the data. These tools include knowledge discovery and data mining (KDD) applications. Many real-world KDD applications involve the analysis of large hierarchies, such as, Internet resources, hot topics on the World Wide Web (WWW), files systems, and organization charts. These large hierarchies can be expressed as hyperbolic trees.
Recently, there has been interest directed to the visual mining (e.g., visual analysis) of large hierarchies with millions of nodes. For example, in web-related data mining, it is desirable for a user to be able to visualize the content and usage of the web. It is a challenge to display millions of documents in a compact and easy-to-visualize format (e.g. on a single screen or display). This display format should facilitate a user's ability to navigate through and to access information from these documents. Using a hyperbolic space representation provides an elegant solution to display large hierarchies on a user screen.
In a directed hierarchical hyperbolic tree, nodes are organized along parent and child relationships. A parent can have many children, but a child can have only one parent. For example, in an organization chart hyperbolic tree, a manager can have many employees, but each employee can report to only one manager. However, in practice, this tree structure may not be sufficient to accurately reflect reality in the workplace. For example, an employee may in reality report to two or more managers (e.g., a regular manager and a temporary project manager). In order to represent these relationships, two paths are needed: (1) one path from the employee to the regular manager, and (2) one path from the employee to the temporary project manager.
Even this simple example suggests that strict hierarchical tree structures are often too restrictive since there are often relationships that need to be linked to a different branch of the tree. The links to a different branch of the tree are commonly referred to in the art as cross-links, secondary links, non-tree edges, or cross edges.
One prior art approach for representing these cross-links in a hyperbolic space is to draw lines between the nodes that are connected or linked. For example, this prior art approach uses additional lines to depict secondary relationships in the hyperbolic tree. The Hyperbolic Tree Toolkit is a commercially available product from Inxight Software that uses this type of approach.
Unfortunately, when many lines and intersections are introduced to represent the secondary relationships, the display becomes confusing, cluttered and difficult to visualize. Furthermore, for far away nodes that are off the screen, this approach displays “broken” lines that do not terminate in a node on the current display, which can add to the confusion. FIG. 7 illustrates a highly connected hierarchical tree with cycles, such as a cycle that is formed by OfficeProduct, Microsoft BackOffice, and SQL Server. As can be seen, the prior art display of this hierarchical tree is very cluttered, confusing, and very difficult to navigate.
Another prior art approach simply prohibits secondary links limiting the hyperbolic tree to a strict hierarchical structure (i.e., allowing each child to have only a single parent node). Although this approach provides a more un-cluttered display, as discussed previously, many real-world applications can only be realistically modeled by using cross-links to indicate relationships between different elements in a system. For example, Web pages are often organized in a standard book format having a table of contents with different URL addresses listed therein. A user can jump to a particular section in the book (e.g., a particular chapter) by clicking on the appropriate URL. When the user is viewing the first page of the selected chapter, the user may be presented with a menu of options somewhere on that page that lists the table of contents URL. Similarly, if the information contained in this chapter relates to another section in another chapter in the book, a jump-site URL can be provided. Consequently, this approach offer an incomplete solution at best to many applications with cross-relationships requiring more than one parent node for a child node.
In summary, the prior art approaches to displaying relationships between nodes in hyperbolic space offer only tolerable solutions that have much to be desired. These prior art approaches fail to display a clean and easy-to-view hyperbolic space. Instead, these prior art approaches provide displays that often leave the users lost, confused, and overwhelmed with many complex displays.
Based on the foregoing, it is desirable to provide a mechanism that links a large highly connected graph in a hyperbolic space without cluttering the display.